\documentclass{beamer}
\usepackage{ctex}
\usetheme{Madrid}

\author{uncle-lu}
\institute{乌鲁木齐市第一中学}
\title{Bipartite Graph}
\date{\today}

\begin{document}
	\frame{\titlepage}
	
	\section{二分图}
	\subsection{基础概念}
	
	\begin{frame}\frametitle{基础概念}
	
		\textbf{二分图}: 在无向图$G=(V,E)$中 如果集合节点可以划分为$V=L \bigcup R$ 其中 $ L \bigcap R = \emptyset $ 并且边集合$ E $中 $ E = \{ (u,v): u \in L,v \in R \}$
		\pause

		所以二分图是一个没有\textbf{奇环}的图.
		\pause
		
		\textbf{匹配}:一个匹配是边的一个子集$M \subseteq E $ 使得对于所有节点$v \in V$子集$M$中最多有一条边与节点$v$相连。
		
		\pause
		
		如果子集$M$中的某条边与结点$v$相连,则称结点$v$由$M$所匹配;否则,结点$v$就是没有匹配的.
	\end{frame}

	\begin{frame}\frametitle{二分图染色}
		运用DFS交叉染色.

		\pause

		作用:判断奇环.
	\end{frame}

	\begin{frame}\frametitle{基础概念}
		\textbf{最大匹配}:最大基数的匹配.对于任意匹配 $M'$ 有 $|M| \ge |M'|$ 的匹配 $M$ .我们称$M$为最大匹配.
		
		\pause
		
		\textbf{完美匹配/完备匹配}: 对于一个匹配$M$ 如果所有点$V$都是匹配点.则我们称$M$为完美匹配.
	\end{frame}

	\subsection{增广路定理}
	
	\begin{frame}\frametitle{增广路定理}
		\textbf{增广路}:
			在一个二分图的一种匹配情况下,从未盖点出发,依次经过非匹配边,
			匹配边,非匹配边,匹配边...所得到的路径成为交替路。以未盖点作
			为终点的交替路成为增广路.
			
		\pause
		
		在增广路中,非匹配边总是比匹配边多一条,所以互换非匹配边与匹配边,得到的匹配会多一条边.
		
		\pause
		
		增广路的作用是改进匹配.

		\pause
		
		\textbf{一个匹配是最大匹配的充要条件是不存在增广路.}
	\end{frame}

	\subsection{一些结论}

	\begin{frame}\frametitle{一些结论}
		\begin{itemize}
			\item \textbf{最大独立集}:两两互不相邻的节点构成的集合中最大的一个的节点数.
			\pause
			\item 最大独立集大小 = 总点数 - 最大匹配数(在二分图中)
			\pause
			\item \textbf{最小点覆盖}:假如选了一个点就相当于覆盖了以它为端点的所有边,你需要选择最少的点来覆盖图上所有的边。
			\pause
			\item \textbf{König定理}:一个二分图中的最小点覆盖等于这个图中的最大匹配数.
		\end{itemize}
	\end{frame}

	\begin{frame}\frametitle{DAG上的结论}
		\begin{itemize}
			\item \textbf{DAG}:有向无环图
			\pause
			\item \textbf{链}:一个点集,其中任意两点u、v可以到达,要么u能走到v,要么v能走到u.
			\pause
			\item \textbf{反链}:一个点集,其中任意两点均不可达.
			\pause
			\item \textbf{最大反链}:反链中点数最多的一条.
			\pause
			\item 最大反链=最小路径覆盖数.
		\end{itemize}	
	\end{frame}

	\subsection{最小点覆盖}

	\begin{frame}\frametitle{最小路径覆盖数解法}
		\begin{enumerate}
			\item \textbf{最小路径覆盖数}:最小的路径条数，使之成为P的一个路径覆盖
			\pause
			\item 将所有结点 $V$ 拆成 $V'$ 与 $V$.其中$V$表示原DAG点$V$的出点.$V'$表示原DAG点$V$的入点.
			\pause
			\item 如果原DAG中有边$(u,v)$则在新图中建边$(u,v')$.
			\pause
			\item 之后我们在新图中跑最大匹配就好了.
		\end{enumerate}
	\end{frame}

	\begin{frame}
		我们感性的理解一下这个问题.

		\pause

		如果我们在二分图里任增加一个匹配.就相当于这个在这个DAG里加一个路径.

		\pause

		所以我们找到的最大匹配.就是在DAG中选择最多的边.使每个点至多一个指出去的边.使每个点至多一个指向它的边.

		\pause

		这就符合了我们的最小路径覆盖的问题.

	\end{frame}

	\subsection{二分图最大匹配}

	\begin{frame}\frametitle{二分图最大匹配算法}
		\begin{itemize}
			\item Hungary算法  
			
			时间复杂度 $O(V \cdot E)$
			
			http://paste.ubuntu.com/25477934/

			\item HK算法
			
			时间复杂度 $O( \sqrt{V} \cdot E )$
			
			\item 网络流最大流算法
			
			时间复杂度 $O($玄学$)$ 
		\end{itemize}
	\end{frame}

	\begin{frame}\frametitle{最大流解二分图最大匹配}
		\begin{enumerate}
			\pause
			\item　建图
			\pause
				\begin{itemize}
					\item 建立超级源点.二分图$x$组点与源点相连.容量为１.
					\pause
					\item 二分图中任意边$(x,y)$建边.容量为$\infty$.
					\pause
					\item 建立超级汇点.二分图$y$组点与汇点相连.容量为１.
				\end{itemize}
			\pause
			\item 选择$ISAP$,$Dinic$,$EK$等算法
			\pause
			\item 感性的理解一下,其实很好理解为什么.
		\end{enumerate}
	\end{frame}

	\subsection{二分图最大权匹配}

	\begin{frame}\frametitle{二分图最大权匹配算法}
		\begin{itemize}
			\item KM算法
			\item 最小费用最大流.(EK+Spfa)
		\end{itemize}
	\end{frame}

	\subsection{KM算法}

	\begin{frame}\frametitle{KM算法基本概念}
		\begin{itemize}
			\pause
			\item \textbf{可行顶标}:一个结点函数l,使得对于任意边$(x,y)$,有$lx(x)+ly(y) \ge w(x,y)$
			\pause
			\item \textbf{相等子图}:原图$G=(V,E)$的一个子图.包含所有$V$,但是只包含$\{lx(x)+ly(y)=w(x,y) : w \in  W\}$的边.
			\pause
			\item \textbf{定理}:如果一个相等子图有完美匹配.则该匹配是原图的最大权匹配.
		\end{itemize}
	\end{frame}

	\begin{frame}\frametitle{定理}
		\textbf{如果一个相等子图有完美匹配,则该匹配是原图的最大权匹配}.
		\pause
		我们设图$G=(V,E)$的完美匹配为$M$.

		我们再设图$G=(V,E)$的一个相等子图有完美匹配$M*$

		$\because |M*|=\sum_{i=1}^{x}\sum_{j=1}^{y} lx(i)+ly(j)$

		$\therefore |M| \le |M*|$

		$\because  M* \in M$

		$\therefore M* = M$
	\end{frame}

	\begin{frame}\frametitle{KM算法流程}
		\begin{enumerate}
			\item 构造一个初始的可行顶标.$ly(y)=0$,$lx(x)=max(W[x][y])$.
			\item 求相等子图的最大匹配,如果存在完美匹配,算法终止.
			\item 否则适当调整可行顶标,重复步骤2.
		\end{enumerate}
	\end{frame}

	\begin{frame}\frametitle{修改可行顶标}
		对于正在增广的增广路上的所有$X$集合的点减去a,所有$Y$集合的点增加a.
		\pause
		对于任意一条边$(x,y)$我们可以发现:
		\begin{itemize}
			\item 如果点$x,y$均属于增广路.则$lx(x)-a+ly(y)+a=w(x,y)$　边$(x,y)$可行性不变.
			\item 如果点$x,y$均不属于增广路.则$lx(x),ly(y)$不变.边$(x,y)$可行性也不会改变.
			\item 如果点$x$属于增广路,点$y$不属于增广路.$lx(x)+a+ly(y)$ 则$lx(x)+ly(y)$增大.边$(x,y)$不会加入相等子图.可行性不变.
			\item 如果点$x$不属于增广路,点$y$属于增广路,$lx(x)+ly(y)-a$ 则$lx(x)+ly(y)$减小.边$(x,y)$可能会加入相等子图.
			\item 这样进行一波操作,在相等子图中的边还在相等子图.不在相等子图的边有可能加入相等子图.
		\end{itemize}
		\pause
		所以我们可以发现.只有最后一条条件可能加入相等子图.所以常数$a$应该为$\{a=min(lx(x)+ly(y)-w(x,y)):x \in G* || y \in G*\}$($G$为相等子图).

		\pause

		这样就保证了有边可以加入相等子图.

	\end{frame}

	\begin{frame}\frametitle{KM算法博客推荐}
		推倒过程+模板

		http://www.cnblogs.com/wenruo/p/5264235.html

	\end{frame}

	\section{杂题选讲}

	\begin{frame}
		\begin{center}
			\LARGE{\textbf{杂题选讲}}

			注:题目排序仅按心情排序.不按题目难度排序.
		\end{center}
	\end{frame}

	\subsection{Problem1}

	\begin{frame}\frametitle{Problem +1s}
		\begin{beamerboxesrounded}[shadow=true]{[HNOI2006]超级英雄Hero}
			给你一个二分图.求最大匹配.
		\end{beamerboxesrounded}
	\end{frame}

	\begin{frame}\frametitle{Solution}
		任选一个二分图最大匹配算法即可.

		注意读题.

		代码实现:http://uncle-lu.org/archives/299

		From:BZOJ1191	
	\end{frame}

	\subsection{Problem2}
	
	\begin{frame}\frametitle{Problem +2s}
		\begin{beamerboxesrounded}[shadow=true]{Ants}
			给出$n$个白点和$n$个黑点的坐标,要求用$n$条不相交的线段把它们链接起来,其中每条线段恰好链接一个白点,和一个黑点,每个点恰好链接到一条线段.
		\end{beamerboxesrounded}
		$1 \leq n \leq 100$
	\end{frame}

	\begin{frame}\frametitle{Solution}
		构造二分图

		每个黑点与白点链接.权值是两者的欧几里得距离.

		最佳完美匹配就是答案的解.

		根据三角形不等式就可以很轻松的明白为什么是这样.

		代码实现:http://paste.ubuntu.com/25487309/

		From:POJ3565
	\end{frame}


	\subsection{Problem3}

	\begin{frame}\frametitle{Problem +3s}
		\begin{beamerboxesrounded}[shadow=true]{关押罪犯}
			给你一个无向图.让你把无向图中的点分成两个集合.集合之间的边取消.要求两个集合中边权最大值最小.求该最大值.
		\end{beamerboxesrounded}
		数据范围:
		
		对于30\%的数据有$N \leq 15$。
		
		对于70\%的数据有$N \leq 2000，M \leq 50000$
		
		对于100\%的数据有$N \leq 20000，M \leq 100000$
	\end{frame}

	\begin{frame}\frametitle{Solution}
		\begin{itemize}
			\item 算法一:

			用并查集.先按照边权排序.

			如果两点在同一个集合则输出.

			否则将合并到敌人的集合中.

			代码实现:http://paste.ubuntu.com/25494722/

			\pause

			\item 算法二:

			二分答案+染色.

			我们可以轻易的发现.一个很难发现的现象.

			我们枚举出来的最大值.比最大值大的边都链接在两个集合中,我们只需要判断是否是二分图就可以判断答案的正确性.

			代码实现:http://paste.ubuntu.com/25494724/

			\item From:NOIP2010.
		\end{itemize}
	\end{frame}

	\subsection{Problem4}

	\begin{frame}\frametitle{Problem +4s}
		\begin{beamerboxesrounded}[shadow=true]{拦截导弹}
			给出n个三维的导弹，每次拦截只能打x，y，z严格上升的若干个导弹，求最多能一次拦截下多少个导弹，以及最少拦截几次将所有导弹全部拦截。
		\end{beamerboxesrounded}
		所有的坐标都是$[0，10^{6}]$的整数 

		对于30\%的数据满足N < 31 

		对于50\%的数据满足N < 101 

		对于100\%的数据满足N < 1001

	\end{frame}

	\begin{frame}\frametitle{Solution}
		第一问直接排序后n²的dp即可。
		
		第二问我们考虑二分图匹配，连边后转换模型成为最小路径覆盖。

		From:BZOJ2244
	\end{frame}

	\subsection{Problem5}

	\begin{frame}\frametitle{Problem +5s}
		\begin{beamerboxesrounded}[shadow=true]{Antenna Placement}
		给出一个矩阵，矩阵中只有‘＊’和‘o’两种字符，每个‘＊’可以向它上下左右四个方位上同为‘＊’的点连一条边，求最少需要连多少条边才能使所有‘＊’被至少一条边连接。
		\end{beamerboxesrounded}
		$1 \le h \le 40$ 

		$1 \le w \le 10$
	\end{frame}

	\begin{frame}\frametitle{Solution}
		最小路径覆盖.
		
		将所有点拆成两个点.建图.

		做最大匹配.

		该题最小路径覆盖的答案为:所有点数-最大匹配/2.

		代码实现:http://paste.ubuntu.com/25494310/

		From:POJ3020
	\end{frame}


	\subsection{Problem6}

	\begin{frame}\frametitle{Problem +6s}
		\begin{beamerboxesrounded}[shadow=true]{变化序列}
		给出一个序列(0~n-1)，这个序列经过某个变换会成为另外一个序列，但是其中的元素不会改变，给出初始序列与变换后的序列每一位上的“距离”，求字典序最小的变换序列。

		定义距离$D(x,y)=min\{|x-y|,N-|x-y|\}$
		\end{beamerboxesrounded}
		 30\%的数据中$N\le 50$

		 60\%的数据中$N \le 500$

		 100\%的数据中$N \le 10000$
	\end{frame}

	\begin{frame}\frametitle{Solution}

	\end{frame}

\end{document}